package leetcode.f1t100;

/**
 * 字符串s, 表达式p(带*,?), 是否匹配
 * https://leetcode.com/problems/wildcard-matching/
 * @Author lichongxiao
 * @Date 2022/9/27 16:30
 */
public class Q44_WildCardMatching {

    public static boolean isMatch(String s, String p) {
        char[] chars = s.toCharArray();
        char[] pattern = p.toCharArray();
//        return tryMatch(chars, pattern,0,0);
//        int cache[][] = new int[chars.length+1][pattern.length+1];
//        return tryMatchCache(chars,pattern,0,0,cache);
        return tryMatchDp(chars,pattern);
    }

    private static boolean tryMatch(char[] chars, char[] pattern, int i, int j) {
        if(i==chars.length && j == pattern.length){
            return true;
        }
        if(i==chars.length && pattern[j] == '*'){
            return tryMatch(chars,pattern,i,j+1);
        }
        if(i==chars.length || j == pattern.length){
            return false;
        }
        if(pattern[j] == '?'){
            return tryMatch(chars,pattern,i+1,j+1);
        }
        if(pattern[j] == '*'){
            for (int k = 1; k <= chars.length-i; k++) {
                if( tryMatch(chars,pattern,i,j+1) ||tryMatch(chars,pattern,i+k,j+1) || tryMatch(chars,pattern,i+k,j)){
                    return true;
                }
            }
            return false;
        }
        if(chars[i] == pattern[j]){
            return tryMatch(chars,pattern,i+1,j+1);
        }
        return false;
    }

    private static boolean tryMatchCache(char[] chars, char[] pattern, int i, int j, int cache[][]) {
        if(cache[i][j] != 0){
            return cache[i][j] == 1;
        }
        if(i==chars.length && j == pattern.length){
            cache[i][j] = 1;
            return cache[i][j] == 1;
        }
        if(i==chars.length && pattern[j] == '*'){
            if(tryMatchCache(chars,pattern,i,j+1,cache)){
                cache[i][j] = 1;
            }
            return cache[i][j] == 1;
        }
        if(i==chars.length || j == pattern.length){
            cache[i][j] = -1;
            return cache[i][j] == 1;
        }
        if(pattern[j] == '?'){
            if(tryMatchCache(chars,pattern,i+1,j+1,cache)){
                cache[i][j] = 1;
            }
            return cache[i][j] == 1;
        }
        if(pattern[j] == '*'){
            for (int k = 1; k <= chars.length-i; k++) {
                if( tryMatchCache(chars,pattern,i,j+1,cache) ||tryMatchCache(chars,pattern,i+k,j+1,cache) || tryMatchCache(chars,pattern,i+k,j,cache)){
                    cache[i][j] = 1;
                    return cache[i][j] == 1;
                }
            }
            cache[i][j] = -1;
            return cache[i][j] == 1;
        }
        if(chars[i] == pattern[j]){
            if(tryMatchCache(chars,pattern,i+1,j+1,cache)){
                cache[i][j] = 1;
            }
            return cache[i][j] == 1;
        }
        cache[i][j] = -1;
        return cache[i][j] == 1;
    }

    private static boolean tryMatchDp(char[] chars, char[] pattern) {
        boolean dp[][] = new boolean[chars.length+1][pattern.length+1];
        dp[chars.length][pattern.length] = true;
        for (int j = pattern.length-1; j >=0 ; j--) {
            if(pattern[j] == '*'){
                dp[chars.length][j] = dp[chars.length][j+1];
            }
        }

        for (int i = chars.length-1; i >=0 ; i--) {
            for (int j = pattern.length-1; j >=0 ; j--) {
                if(pattern[j] == '?'||chars[i]==pattern[j]){
                    dp[i][j]=dp[i+1][j+1];
                }else if(pattern[j]=='*'){
                    for (int k = 1; k <= chars.length-i; k++) {
                        dp[i][j] = dp[i][j+1] || dp[i+k][j+1] || dp[i+k][j];
                        if(dp[i][j]){
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0];
    }

    /**
     *
     * @param str
     * @param pattern
     * @return
     */
    private static boolean comparison(String str, String pattern) {
        int s = 0, p = 0, match = 0, starIdx = -1;
        while (s < str.length()){
            // advancing both pointers
            if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                s++;
                p++;
            }
            // * found, only advancing pattern pointer
            else if (p < pattern.length() && pattern.charAt(p) == '*'){
                starIdx = p;
                match = s;
                p++;
            }
            // last pattern pointer was *, advancing string pointer
            else if (starIdx != -1){
                p = starIdx + 1;
                match++;
                s = match;
            }
            //current pattern pointer is not star, last patter pointer was not *
            //characters do not match
            else return false;
        }

        //check for remaining characters in pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
            p++;

        return p == pattern.length();
    }

    public static void main(String[] args) {
//        System.out.println(isMatch("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b"));
        System.out.println(isMatch("a","*a"));
        System.out.println(comparison("abca","*a"));

    }


}
